package org.example.day03;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO
 * 给定M(0&lt;M&lt;=30)个字符（a-z），从中取出任意字符（每个字符只能用一次）拼接成长度为N(0&lt;N&lt;=5)的字符串，要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回0。<br>
 *
 * 给定M(0<M<=30)个字符（a-z），从中取出任意字符（每个字符只能用一次）拼接成长度为N(0<N<=5)的字符串，
 * 要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回0。
 * @date 2024/3/11 15:22
 */
public class test058 {
    // 递归函数，用于计算满足条件的字符串数量
    private static int countUniqueStrings(char[] chars, int n, int index, boolean[] used, StringBuilder current) {
        if (index == n) {
            // 当前字符串长度等于N，找到一个满足条件的字符串
            return 1;
        }

        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (!used[i] && (index == 0 || chars[i] != current.charAt(index - 1))) {
                // 如果字符未被使用，并且（当前位置是第一个字符或者当前字符与前一个字符不同）
                used[i] = true; // 标记字符为已使用
                current.append(chars[i]); // 将字符添加到当前字符串
                count += countUniqueStrings(chars, n, index + 1, used, current); // 递归调用
                current.deleteCharAt(index); // 回溯，移除当前字符
                used[i] = false; // 标记字符为未使用
            }
        }

        return count;
    }

    // 主函数，用于计算并返回满足条件的字符串数量
    public static int countUniqueStrings(char[] chars) {
        int n = chars.length; // 字符列表的长度
        if (n == 0 || n > 30) {
            return 0; // 输入非法，字符数量不在指定范围内
        }

        int maxLength = 5; // 字符串的最大长度
        if (n < maxLength) {
            maxLength = n; // 如果字符数量小于最大长度，则最大长度应为字符数量
        }

        // 初始化用于跟踪字符使用情况的数组和StringBuilder
        boolean[] used = new boolean[n];
        StringBuilder current = new StringBuilder();

        // 计算所有可能的字符串数量
        int totalCount = 0;
        for (int length = 1; length <= maxLength; length++) {
            totalCount += countUniqueStrings(chars, length, 0, used, current);
        }

        return totalCount;
    }

    // 测试方法
    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c'};
        System.out.println(countUniqueStrings(chars)); // 输出应为6，即："abc", "acb", "bac", "bca", "cab", "cba"

        chars = new char[]{'a', 'b', 'a', 'c'};
        System.out.println(countUniqueStrings(chars)); // 输出应为0，因为相同字符不能相邻

        chars = new char[]{'a', 'b', 'c', 'd', 'e'};
        System.out.println(countUniqueStrings(chars)); // 输出应为更多，具体数量取决于递归计算
    }
}
